Cả Phobos và Deimos đều được nhà thiên văn học Mỹ là Asaph Hall phát hiện. Tên của hai vệ tinh này được Henry Madan (1838–1901), giáo sư toán học Eton College đề xuất từ cuốn XV tác phẩm Iliad, theo tên hai con thần chiến tranh Ares (Mars trong thần thoại La Mã) là Kinh hoàng (Deimos) và Khiếp sợ (Phobos).

Deimos được phát hiện ngày 12 tháng 8 năm 1877 lúc khoảng 07:48 UTC (theo những nguồn tin thời ấy là lúc "14:40 11 tháng 8" theo giờ Washington tính ngày theo quy ước thiên văn cũ, bắt đầu vào lúc giữa trưa, vì thế phải cộng thêm 12 tiếng vào giờ địa phương) .